import copy
import random

def IntGenerator(num:int=500,rho:float=0.2):
    """
    不重复整数生成器
    Args:
        num: 列表大小，default 500
        rho: 随机采样率，default 0.2
    """
    memory=set()
    Rrange = num/rho//2
    while num:
        num-=1
        a = random.randint(1,2*Rrange+1)
        while a in memory:
            a = random.randint(1,2*Rrange+1)
        memory.add(a)
        yield a

class HashTable(object):
    def __init__(self,lam:float=0.7) -> None:
        self.__size_generator = self.prime_generator()
        self.__size = 0
        self.__lam_expect = lam
        self.__used_index = 0
        self.__max_step = 0

    def __set_size(self,size):
        self.__size=size
        self.keys=[None]*self.__size
        self.values=[None]*self.__size
    
    def __update_params(self,args):
        (self.__size,self.__lam_expect,self.__used_index,
         self.__max_step,self.keys,self.values) = args
        
    def __get__params(self):
        return (self.__size,self.__lam_expect,self.__used_index,
                self.__max_step,self.keys,self.values)

    def __hashfunction(self,key):
        return key%self.__size
    
    def __odd_maker(self):
        t = -1
        self.__search_step = 0
        def odd():
            self.__search_step+=1
            nonlocal t
            t+=2
            if t%self.__size==0:
                t+=2
            return t
        return odd
    
    def prime_generator(self):
        def odd():
            i = 1
            while True:
                i+=2
                yield i
        def _not_divisible(n):
            return lambda x: x % n > 0
        it_genor = odd()
        while True:
            prime = next(it_genor)
            if prime >= self.__size:
                yield prime
            it_genor = filter(_not_divisible(prime) ,it_genor)
    
    def __rehash(self,key):
        return self.__hashfunction(key+self.odd())

    def __check_lam(self):
        size_is_change = False
        while self.__used_index/self.__size >= self.__lam_expect:
            self.__size=next(self.__size_generator)
            size_is_change = True
        if not size_is_change :
            return None
        
        HashTable_temp=HashTable()
        HashTable_temp.__set_size(self.__size)
        for i,key in enumerate(self.keys):
            if key==None:
                continue
            HashTable_temp.put(key,self.values[i])

        self.__update_params(HashTable_temp.__get__params())

    def __change_table(index,key,value,keys,values):
        keys[index] = key
        values[index] = value
        return keys,values

    def put(self,key,value):
        if self.__size == 0:
            self.__size = 9
            self.__size = next(self.__size_generator)
            self.__set_size(self.__size)
        
        self.__check_lam()

        self.odd=self.__odd_maker()
        hashindex = self.__hashfunction(key)
        while True:
            if self.keys[hashindex] in (None,key):
                if self.keys[hashindex] == None:
                    self.__used_index+=1
                self.keys,self.values = HashTable.__change_table(
                    hashindex,key,value,self.keys,self.values)
                break
            if self.__search_step > (self.__size+1)/2:
                raise ValueError("error rehash")
            hashindex = self.__rehash(hashindex)
        if self.__search_step > self.__max_step:
            self.__max_step=self.__search_step
        del self.odd

    def get(self,key):
        hashindex = self.__hashfunction(key)

        try_times=0
        self.odd=self.__odd_maker()
        while try_times <= self.__max_step: 
            if self.keys[hashindex] == key:
                result = self.values[hashindex]
                break
            hashindex=self.__rehash(hashindex)
            try_times+=1
        else:
            result = None 
        del self.odd

        return result 

    def __len__(self):
        return self.__used_index

    def __contains__(self,keytest):
        return keytest in self.keys

    def __getitem__(self,key):
        return self.get(key)
    
    def __setitem__(self,key,value):
        self.put(key,value)

    def __delitem__(self,key):
        self.odd=self.__odd_maker()
        hashindex = self.__hashfunction(key)
        while True:
            if self.keys[hashindex] == key:
                self.__used_index-=1
                self.keys,self.values = HashTable.__change_table(
                    hashindex,None,None,self.keys,self.values)
                break
            hashindex = self.__rehash(hashindex)
        if self.__search_step > self.__max_step:
            self.__max_step=self.__search_step
        del self.odd


def main(N=1000):
    H=HashTable(lam=0.5)
    keys=list()
    for key in IntGenerator(N):
        keys.append(key)
        H[key]=key+114514
    for key in keys:
        if H[key] != key+114514:
            print("error")
            break
    else:
        print("pass")
    H[114514]="test"
    print(H[114514]) # 应该为 test
    del H[114514]
    print(H[114514]) # 应该为 None
    print(len(H))    # 应该为 N=1000

if __name__ == "__main__":
    main()
